package com.ljy.my_study.leetcode.跳跃游戏IV;

import java.util.*;

/**
 * @Description:
 * @Author: li.junying
 * @date: 2022-01-21 09:39
 */
public class TestMain {

    public static void main(String[] args) {
        int[] arr={100,-23,-23,404,100,23,23,23,3,404};
        System.out.println(new TestMain().minJumps(arr));
    }

    public int minJumps(int[] arr) {
        Map<Integer, List<Integer>> map=new HashMap<>();
        int len=arr.length;
        for(int i=0;i<len;i++){
            List<Integer> list= map.getOrDefault(arr[i],new ArrayList<>());
            list.add(i);
            map.put(arr[i],list);
        }
        int[] visitedCount=new int[len];
        Arrays.fill(visitedCount,Integer.MAX_VALUE);
        boolean[] visited=new boolean[len];
        visited[0]=true;
        return dfs(0,map,arr,visitedCount,0,Integer.MAX_VALUE);
    }

    private int dfs(int index,Map<Integer,List<Integer>> map,int[] arr,int[] visitedCount,int step,int finalStep){
        int len=visitedCount.length;
        if(step>=finalStep){
            return finalStep;
        }
        if(index==len-1){
            return Math.min(step,finalStep);
        }
        int minFinalStep=finalStep;
        // 1.跳躍
        if(map.containsKey(arr[index])){
            List<Integer> list=map.get(arr[index]);
            for(int i=0;i<list.size();i++){
                int nextIndex=list.get(i);
                if(visitedCount[nextIndex]<step+1){
                    continue;
                }
                visitedCount[nextIndex]=step+1;
                minFinalStep=Math.min(minFinalStep,dfs(nextIndex,map,arr,visitedCount,step+1,finalStep));
            }
        }

        // 2.往前走
        if(index+1<len){
            int nextIndex=index+1;
            if(visitedCount[nextIndex]>step+1){
                visitedCount[nextIndex]=step+1;
                minFinalStep=Math.min(minFinalStep,dfs(nextIndex,map,arr,visitedCount,step+1,finalStep));
            }
        }

        // 3.往後走
        if(index-1>=0){
            int nextIndex=index-1;
            if(visitedCount[nextIndex]>step+1){
                visitedCount[nextIndex]=step+1;
                minFinalStep=Math.min(minFinalStep,dfs(nextIndex,map,arr,visitedCount,step+1,finalStep));
            }
        }
        return minFinalStep;
    }
}
